"""
leetcode 739 每日温度

给定一个按照日期排列的温度列表，对于列表中的每个元素，计算需要等待多久温度才会超过当前温度。如果不存在超过当前温度的温度，对应的返回值为0。例如，给定一个列表temperature = [73, 74, 75, 71, 69, 72, 76, 73]，对应的输出应该为[1, 1, 4, 2, 1, 1, 0, 0]。

思路：与496下一个更大的元素类似，496是给定两个无重复元素的列表，找到列表1的所有元素在列表2中对应位置后面的第一个更大的值；739是给定一个可能含重复元素的列表，找到列表中每个元素与下一个更大元素的距离。采取相似的思路，维护一个递减栈来保存列表的元素对应的下标，初始化一个与给定列表等长的零列表来保存结果（由于列表可能含有重复元素，不能使用集合或者字典），从左到右遍历列表，若栈非空，且当前索引对应的元素值大于栈顶索引对应的元素值，则栈顶索引出栈，将栈顶索引对应的结果置为当前索引与栈顶索引之差；否则当前索引入栈。

复杂度分析：每个元素入栈一次，最多出栈一次（无下一个更大元素的元素不出栈），时间复杂度O(N)；空间复杂度O(N)。
"""
from typing import List


class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        # 找到数组中第一个大于当前元素的值所在的位置
        # 单调非递增栈，栈内存下标，哈希表
        stack = []
        ans = [0] * len(T)
        for i in range(len(T)):
            while stack and T[i] > T[stack[-1]]:
                index = stack.pop()
                ans[index] = i-index
            else:
                stack.append(i)
        return ans
